package com.promote.algorithm;

/**
 * @ClassName MaxProfit
 * Description 买卖股票的最佳时机
 * @Author LiZiHao
 * Date 2022/3/3 16:54
 * @Version 1.0
 **/
public class MaxProfit {

    /**
     * 动态规划的方式  买卖股票的最佳时机 II
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int dp0 = 0;
        int dp1 = -prices[0];

        for (int i= 1; i < n; ++i) {
            int newDp0 = Math.max(dp0,dp1 + prices[i]);
            int newDp1 = Math.max(dp1,dp0 - prices[i]);

            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
}
